#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 300
typedef int MatrizAdjacencia[N][N];
typedef int removedVec[N];
typedef int List[N];
/**
 * Estrutura de dados que marca os nós presentes.
 * Para todos i entre 0 e 99, inclusive, o vetor vale
 * 1, caso o nó i enteja presente, ou 0, caso contrário.
 */
typedef struct
{
	int *l;
	int size;
	int maxSize;
	int firstNode;
} ListOfNodes;

typedef struct
{
	MatrizAdjacencia matrix;
	int n;
	int m;
} Graph;

typedef struct
{
	int pos;
	int deg;
} PosAndDeg;

void clearMatrix (MatrizAdjacencia matrix)
{
	int i, j;

	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			matrix[i][j] = 0;
}

ListOfNodes setupList (int maxSize, List L)
{
	ListOfNodes new;

	new.l = L;
	new.size = 0;
	new.maxSize = maxSize;
	new.firstNode = -1;

	return new;
}

void freeList (ListOfNodes *list)
{
	free(list->l);
}

int isThereNode (ListOfNodes *list, int pos)
{
	return list->l[pos];
}

ListOfNodes copyList (ListOfNodes *original, List L)
{
	ListOfNodes new;
	int i;

	new = setupList(original->maxSize, L);
	new.firstNode = original->firstNode;
	new.maxSize = original->maxSize;
	new.size = original->size;

	for (i = 0; i < original->maxSize; i++)
		new.l[i] = original->l[i];

	return new;

}

Graph shallowCopyGraph (Graph g)
{
	return g;
}

int nodeDegree (ListOfNodes *list, int pos, MatrizAdjacencia matrix)
{
	int i, deg;

	for (i = 0, deg = 0; i < list->maxSize; i++)
		if (i != pos)
			deg += matrix[pos][i];

	return deg;
}

PosAndDeg nodeWithHighestDegree (ListOfNodes *list, MatrizAdjacencia matrix)
{
	int i, pos, maxDeg, deg;

	PosAndDeg p;

	for (i = 0, pos = 0, maxDeg = -1; i < list->maxSize; i++)
	{
		if (isThereNode(list, i))
		{
			deg = nodeDegree(list, i, matrix);
			if (deg > maxDeg)
			{
				maxDeg = deg;
				pos = i;
			}
		}
	}

	p.pos = pos;
	p.deg = maxDeg;

	return p;
}

void setFirstNode (ListOfNodes *list, int offset)
{
	int i;

	for (i = offset + 1; i < list->maxSize; i++)
	{
		if (list->l[i])
		{
			list->firstNode = i;
			return;
		}
	}

	list->firstNode = -1;
	return;
}

int removeNode (int nodePos, ListOfNodes *list)
{
	if (nodePos >= 0 && list->l[nodePos])
	{
		list->size--;

		list->l[nodePos] = 0;

		if (list->firstNode == nodePos)
			setFirstNode(list, nodePos);

		return 1;
	}

	return 0;
}

int kRemoveNodeAndAdjacency (int nodePos, ListOfNodes *list, removedVec v, MatrizAdjacencia matrix)
{
	int i;

	if (!removeNode(nodePos, list))
		return 0;


	for (i = 0; i < list->maxSize; i++)
	{
		v[i] = 0;
		if (matrix[nodePos][i] == 1)
			if (removeNode(i, list))
				v[i] = 1;
	}

	v[nodePos] = 1;
	return 1;
}

void removeNodeAndAdjacency (int nodePos, ListOfNodes *list, MatrizAdjacencia matrix)
{
	int i;

	for (i = 0; i < list->maxSize; i++)
	{
		if (isThereNode(list, i) && matrix[nodePos][i] == 1 && nodePos != i)
			removeNode(i, list);
	}

	removeNode(nodePos, list);
}

int addNode (int nodePos, ListOfNodes *list)
{
	if (nodePos >= 0 && !(list->l[nodePos]))
	{
		list->size++;

		list->l[nodePos] = 1;

		if (nodePos < list->firstNode)
			list->firstNode = nodePos;

		return 1;
	}

	return 0;
}

int kAddNodeAndAdjacency (int nodePos, ListOfNodes *list, removedVec v)
{
	int i;

	if (!addNode(nodePos, list))
		return 0;

	v[nodePos] = 0;

	for (i = 0; i < list->maxSize; i++)
	{
		if (v[i])
			addNode(i, list);
	}

	return 1;
}

int getFirstNode(ListOfNodes *list)
{
	int i;

	for (i = 0; i < list->maxSize; i++)
	{
		if (list->l[i] == 1)
			return i;
	}

	return -1;
}

/**
 * Função que adiciona a aresta a-b à Matriz de Adjacência matrix
 */
void addEdge (int a, int b, MatrizAdjacencia matrix)
{
	//printf("Adicionou-se aresta %d-%d\n", a, b);

	matrix[a][b] = 1;
	matrix[b][a] = 1;
}

/**
 * Função que remove a aresta a-b da Matrix de Adjacência matrix
 */
void removeEdge (int a, int b, MatrizAdjacencia matrix)
{
	matrix[a][b] = 0;
	matrix[b][a] = 0;
}

int max (int a, int b)
{
	return a > b ? a : b;
}

unsigned int coreA1(ListOfNodes *list, MatrizAdjacencia M)
{
	ListOfNodes copy;
	int m;
	List L;

	// Casos base
	if (list->size == 1)
	{
		return 1;
	}
	else if (list->size <= 0)
	{
		return 0;
	}

	copy = copyList(list, L);

	removeNode(list->firstNode, &copy);						//Nó não presente
	removeNodeAndAdjacency(list->firstNode, list, M);		//Nó presente

	m = max(coreA1(&copy, M), 1 + coreA1(list, M));

	return m;
}

unsigned int coreA2(ListOfNodes *list, MatrizAdjacencia M)
{
	ListOfNodes copy;
	int m, aux;
	int i;
	List L;

	// Casos base
	if (list->size == 1)
	{
		return 1;
	}
	else if (list->size == 0)
	{
		return 0;
	}

	for (i = 0; i < list->maxSize; i++)
	{
		if (isThereNode(list, i))
		{
			aux = nodeDegree(list, i, M);

			if (aux < 2)
			{
				if (aux == 0)
				{
					removeNode(i, list);
					return 1 + coreA2(list, M);
				}
				else
				{
					removeNodeAndAdjacency(i, list, M);
					return 1 + coreA2(list, M);
				}
			}
		}
	}

	copy = copyList(list, L);

	removeNode(list->firstNode, &copy);						//Nó não presente
	removeNodeAndAdjacency(list->firstNode, list, M);		//Nó presente

	m = max(coreA2(&copy, M), 1 + coreA2(list, M));

	return m;
}

unsigned int coreA3(ListOfNodes *list, MatrizAdjacencia M)
{
	ListOfNodes copy;
	int m, aux;
	PosAndDeg toRemove;
	int i;
	List L;

	// Casos base
	if (list->size == 1)
	{
		return 1;
	}
	else if (list->size == 0)
	{
		return 0;
	}

	for (i = 0; i < list->maxSize; i++)
	{
		if (isThereNode(list, i))
		{
			aux = nodeDegree(list, i, M);

			if (aux < 2)
			{
				if (aux == 0)
				{
					removeNode(i, list);
					return 1 + coreA2(list, M);
				}
				else
				{
					removeNodeAndAdjacency(i, list, M);
					return 1 + coreA2(list, M);
				}
			}
		}
	}

	copy = copyList(list, L);

	toRemove = nodeWithHighestDegree(list, M);

	removeNode(toRemove.pos, &copy);								//Nó não presente
	removeNodeAndAdjacency(toRemove.pos, list, M);					//Nó presente

	m = max(coreA3(&copy, M), 1 + coreA3(list, M));

	return m;
}

unsigned int A1(unsigned int n, MatrizAdjacencia M)
{
	ListOfNodes list;
	List L;
	int i;
	unsigned int m;

	list = setupList(n, L);
	list.size = n;
	list.firstNode = 0;

	for (i = 0; i < n; i++)
	{
		list.l[i] = 1;
	}

	m = coreA1(&list, M);

	return m;
}

unsigned int A2(unsigned int n, MatrizAdjacencia M)
{
	ListOfNodes list;
	int i;
	unsigned int m;
	List L;

	list = setupList(n, L);
	list.size = n;
	list.firstNode = 0;

	for (i = 0; i < n; i++)
	{
		list.l[i] = 1;
	}

	m = coreA2(&list, M);

	return m;
}

unsigned int A3(unsigned int n, MatrizAdjacencia M)
{
	ListOfNodes list;
	int i;
	unsigned int m;
	List L;

	list = setupList(n, L);
	list.size = n;
	list.firstNode = 0;

	for (i = 0; i < n; i++)
	{
		list.l[i] = 1;
	}

	m = coreA3(&list, M);

	return m;
}

double A1Handler (int n, MatrizAdjacencia M)
{
	int card;
	clock_t t1, t2;

	t1 = clock();
	card = A1(n, M);
	t2 = clock();

	printf("Cardinality according to A1: %d\n", card);

	return ((double)t2 - (double)t1) / CLOCKS_PER_SEC;
}

double A2Handler (int n, MatrizAdjacencia M)
{
	int card;
	clock_t t1, t2;

	t1 = clock();
	card = A2(n, M);
	t2 = clock();

	printf("Cardinality according to A2: %d\n", card);

	return ((double)t2 - (double)t1) / CLOCKS_PER_SEC;
}

double A3Handler (int n, MatrizAdjacencia M)
{
	int card;
	clock_t t1, t2;

	t1 = clock();
	card = A3(n, M);
	t2 = clock();

	printf("Cardinality according to A3: %d\n", card);

	return ((double)t2 - (double)t1) / CLOCKS_PER_SEC;
}

/**
 * Função de geração de grafos aleatórios.
 * O grafo retornado possui n nós e m arestas.
 */
Graph graphMaker (int n, int m)
{
	static int initialized = 0;
	Graph g;
	int i, j;

	g.n = n;
	g.m = 0;
	clearMatrix(g.matrix);

	if (!initialized)
	{
		srand48(clock());
		initialized = 1;
	}

	while (g.m < m)
	{
		i = (int) (n + 1) * drand48();
		j = (int) (n + 1) * drand48();

		if (!g.matrix[i][j] && (i != j))
		{
			g.m++;
			addEdge(i, j, g.matrix);
		}
	}

	return g;
}

void algTester (int iter, int n, int m)
{
	int i;
	Graph g1, g2, g3;

	for (i = 0; i < iter; i++)
	{
		g1 = g2 = g3 = graphMaker(n, m);

		printf("--Iteration %d--\n\n", i);

		printf("A1-ET: %fs\n\n", A1Handler(g1.n, g1.matrix));
		printf("A2-ET: %fs\n\n", A2Handler(g2.n, g2.matrix));
		printf("A3-ET: %fs\n\n", A3Handler(g3.n, g3.matrix));
		printf("\n");
	}
}

void algTesterWrap (void)
{
	int iter, n, m;

	printf("# of iterations: ");
	scanf("%d", &iter);
	printf("# of nodes: ");
	scanf("%d", &n);
	printf("# of edges: ");
	scanf("%d", &m);

	algTester(iter, n, m);
}

void IOHandler (void)
{
	int ng, n, m;
	int i, j;
	int v1, v2;
	MatrizAdjacencia M;

	scanf("%d %d %d", &ng, &n, &m);

	for (i = 0; i < ng; i++)
	{
		clearMatrix(M);
		for (j = 0; j < m; j++)
		{
			scanf("%d %d", &v1, &v2);

			M[v1][v2] = 1;
			M[v2][v1] = 1;
		}

		printf("Graph #%d\n", i);
		printf("A1-ET: %fs\n", A1Handler(n, M));
		printf("A2-ET: %fs\n", A2Handler(n, M));
		printf("A3-ET: %fs\n", A3Handler(n, M));
	}
}

int main (void)
{
	IOHandler();

	//algTesterWrap();

	return 0;
}
